11190. Серия степеней
По заданным l,
h и k вычислить сумму степеней:
S(l, h, k) = lk
+ (l + 1)k + (l + 2)k + … + (h – 1)k + hk
Вход. Содержит
не более 1500 тестов. Каждый тест содержит три целых числа l, h (0 £ l £ h £ 15000000, |l – h| £ 1000) и k (1 £ k £ 15000000). Последний тест содержит три минус единицы и не обрабатывается.
Выход. Для каждого теста вывести приблизительное значение S(l,
h, k) в формате 0.ddddddedddddddddd. Значение мантиссы всегда меньше 1, она содержит 6 знаков после
десятичной точки. Если значение экспоненты не существенно, установите ее равной
1.
Пример входа
1 10 10
10 15 100
-1 -1 -1
Пример выхода
Case 0001: 0.149143e0000000011
Case 0002: 0.406971e0000000118
РЕШЕНИЕ
математика
Анализ алгоритма
Представим каждое слагаемое ik в виде 
. Например,
экспонента числа hk = 
равна exponent = 
. Поскольку |l – h| £ 1000, то экспонента остальных степеней не сильно будет
отличаться от . Поэтому вместо суммирования слагаемых ik будем суммировать 
= 
= 
. При таком суммировании значение мантисы не будет слишком
большим и для ее нахождения достаточно воспользоваться типом double.
Отдельно следует обработать случай, когда искомая сумма равна нулю. Тогда мантису следует установить равной
нулю, а экспоненту равной 1.
Реализация алгоритма
Читаем входные данные.
while(scanf("%d %d %d",&l,&h,&k),l + h +
k > 0)
{
Обнуляем текущее значение мантисы s. Вычисляем экспоненту exponent
значения hk = .
s = 0; exponent = k*log10(1.0*h);
Прибавляем к мантисе s значение
.
for(i = l;
i <= h; i++)
s += pow(10,k*log10(1.0*i) - exponent);
Если мнтиса не меньше 1, то делаем ее таковой.
while (s
>= 1) s /= 10, exponent++;
Исключительный случай может возникнуть, когда результат
суммы равен 0. Тогда мантиса равна нулю, а значение экспоненты не существенно.
Устанавливаем s = 0, exponent = 1
if (!h) s =
0, exponent = 1;
printf("Case
%04d: %.6lfe%010d\n", cs++, s, exponent);
}